<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <link rel="stylesheet" href="css/prism.css">
  <style>
    html,
    body {
      box-sizing: border-box;
      margin: 0;
      padding: 0;
      height: 100%;
      font-size: 12px;
    }

    body {
      min-height: 500px;
    }

    section {
      display: flex;
      flex-wrap: wrap;
    }

    .code {
      margin-top: 3px;
    }

    pre[class*=language-] {
      margin: 0;
      padding: 0;
    }

    main {
      border-top: 2px solid #ccc;
      width: 100%;
      height: 68%;
      min-height: 200px;
    }
  </style>
  <title>二叉搜索树</title>
</head>

<body>
  <section class="frames"></section>
  <section style="display: none;">
    <pre><code class="language-java">int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}</code></pre>
  </section>
  <main></main>
  <section>
    <div style='background-color:#f08d49; margin: 2px 2px 0 0; padding: 4px 6px;'>前驱或后继</div>
    <div style='background-color:#f0ff1c; margin: 2px 2px 0 0; padding: 4px 6px;'>祖先自左而来</div>
    <div style='background-color:#ff371c; margin: 2px 2px 0 0; padding: 4px 6px;'>祖先自右而来</div>
    <div style='background-color:#00FF99; margin: 2px 2px 0 0; padding: 4px 6px;'>找到节点</div>
    <div style='background-color:#ccc; margin: 2px 2px 0 0; padding: 4px 6px;'>未访问</div>
  </section>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>数组表示的二叉树&nbsp;</span><input type="text" id='data' class="saveable" value="4,2,6,1,3,5,7">
    <span>n&nbsp;</span><input type="text" id='n' class="saveable" value="5">
    <span>动画速度(ms)&nbsp;</span><input type="number" step="100" value="300" id="animate_speed" class="saveable">
    <input style='font-size:12px;' type="button" value="保存" onclick="onSave('tree_binary_search')">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>待查找 key</span><input type="text" id='key' class="saveable" value="1">
    <input style='font-size:12px;' type="button" value="get" onclick="doGet()">
    <input style='font-size:12px;' type="button" value="min" onclick="doMin()">
    <input style='font-size:12px;' type="button" value="max" onclick="doMax()">
    <input style='font-size:12px;' type="button" value="predecessor" onclick="doPredecessor()">
    <input style='font-size:12px;' type="button" value="successor" onclick="doSuccessor()">
    <input style='font-size:12px;' type="button" value="例1" onclick="e1()">
    <input style='font-size:12px;' type="button" value="例2" onclick="e2()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>待插入 key</span><input type="text" id='inserted' class="saveable" value="9">
    <input style='font-size:12px;' type="button" value="put" onclick="doPut()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>待删除 key</span><input type="text" id='deleted' class="saveable" value="4">
    <input style='font-size:12px;' type="button" value="delete" onclick="doDelete()">
    <input style='font-size:12px;' type="button" value="删1" onclick="e3()">
    <input style='font-size:12px;' type="button" value="删2" onclick="e4()">
    <input style='font-size:12px;' type="button" value="删3" onclick="e5()">
    <input style='font-size:12px;' type="button" value="删4" onclick="e6()">
  </div>
  <script src="js/p5.js"></script>
  <script src="js/p5-svg.js"></script>
  <script src="js/util.js"></script>
  <script src="js/prism.js"></script>
  <script>
    function e1() {
      document.getElementById("data").value = '4,2,7,1,3,6,8,n,n,n,n,5'
      onSave('tree_binary_search')
    }
    function e2() {
      document.getElementById("data").value = '5,2,7,1,3,6,8,n,n,n,4'
      onSave('tree_binary_search')
    }
    function e3() {
      document.getElementById("data").value = '3,n,4,n,n,n,7,n,n,n,n,n,n,6'
      onSave('tree_binary_search')
    }
    function e4() {
      document.getElementById("data").value = '6,4,n,2,n,n,n,1,3'
      onSave('tree_binary_search')
    }
    function e5() {
      document.getElementById("data").value = '7,4,n,2,5,n,n,1,3,n,6'
      onSave('tree_binary_search')
    }
    function e6() {
      document.getElementById("data").value = '4,2,8,n,n,7,9,n,n,n,n,5,n,n,n,n,n,n,n,n,n,n,n,n,6'
      onSave('tree_binary_search')
    }
    const colorMap = new Map()
    const colorArray = ['#1abc9c', '#e67e22', '#3498db', '#f1c40f', '#9b59b6', '#e74c3c']
    let colorIndex = 0
    const options = loadOptionsFromStorage('tree_binary_search')
    let data = options.data.split(',').map(e => {
      if (e === 'null' || e === 'n') {
        return null
      } else {
        return e;
      }
    })
    const DIAMETER = 25                   // 直径 diameter
    const n = options.n
    const d = new Draw(options.animate_speed)
    let root
    function preload() {
      // const font = loadFont('JetBrainsMono-Regular.ttf')
    }
    function setup() {
      const WIN_WIDTH = document.querySelector('main').clientWidth
      const WIN_HEIGHT = document.querySelector('main').clientHeight
      const FONT_SIZE = 14
      createCanvas(WIN_WIDTH, WIN_HEIGHT, SVG)
      textSize(FONT_SIZE)
      textAlign(CENTER)
      noStroke()
      root = binary_tree(data, n)
      d.updateFrameButtons()
    }
    function draw() {
      d.draw(() => background('#2d2d2d'))
    }
    function frame({ cloned, ancestorFromLeft, ancestorFromRight }) {
      drawTree(cloned, width / 2, DIAMETER / 2 + 4, n - 1, 0, 0, ancestorFromLeft, ancestorFromRight)
    }

    function drawTree(node, x, y, deep, px, py, ancestorFromLeft, ancestorFromRight) {
      if (node) {
        if (node.txt) {
          if (px && py) {
            stroke('white')
            line(x, y, px, py)
            noStroke()
          }
        }
        drawTree(node.left, x - Math.pow(2, deep) * DIAMETER / 4, y + Math.pow(2, n - deep) * DIAMETER / 2, deep - 1, x, y, ancestorFromLeft, ancestorFromRight)
        drawTree(node.right, x + Math.pow(2, deep) * DIAMETER / 4, y + Math.pow(2, n - deep) * DIAMETER / 2, deep - 1, x, y, ancestorFromLeft, ancestorFromRight)
        if (node.txt) {
          if (ancestorFromLeft && ancestorFromLeft == node.txt) {
            fill('#f0ff1c'); circle(x, y, DIAMETER + 4)
          }
          if (ancestorFromRight && ancestorFromRight == node.txt) {
            fill('#ff371c'); circle(x, y, DIAMETER + 4)
          }

          if ((node.status & 1) === 1) { fill('#00FF99') } else { fill('#ccc') }
          arc(x, y, DIAMETER, DIAMETER, PI, TWO_PI)
          if ((node.status & 2) === 2) { fill('#00FF99') } else { fill('#ccc') }
          arc(x, y, DIAMETER, DIAMETER, HALF_PI, PI)
          if ((node.status & 4) === 4) { fill('#00FF99') } else { fill('#ccc') }
          arc(x, y, DIAMETER, DIAMETER, 0, HALF_PI)
          if ((node.status & 8) === 8) { fill('#f08d49'); circle(x, y, DIAMETER) }

          fill('black')
          text(node.txt, x, y + 4)
        }
      }
    }

    function doDelete() {
      clearStatus(root)
      const key = Number(document.getElementById("deleted").value)
      let node = root
      let parent = null
      while (node != null) {        
        if (key < node.txt) {
          parent = node
          node.status |= 2
          d.add({ cloned: clone(root) }, frame)
          node = node.left
        } else if (node.txt < key) {
          parent = node
          node.status |= 4
          d.add({ cloned: clone(root) }, frame)
          node = node.right
        } else {
          node.status |= 7
          d.add({ cloned: clone(root) }, frame)
          break
        }
      }
      if (node == null) {
        d.updateFrameButtons()
        return null
      }      
      if (!node.left) {
        shiftNode(parent, node, node.right)
      } else if (!node.right) {
        shiftNode(parent, node, node.left)
      } else {
        let sparent = node
        let s = node.right
        while (s.left) {
          sparent = s
          s = s.left
        }
        s.status |= 8
        d.add({ cloned: clone(root) }, frame)
        if (sparent != node) {
          shiftNode(sparent, s, s.right)
          s.right = node.right
          d.add({ cloned: clone(root) }, frame)
        }        
        shiftNode(parent, node, s)
        s.left = node.left
      }
      d.add({ cloned: clone(root) }, frame)
      d.updateFrameButtons()
      return node
    }

    function shiftNode(n1Parent, n1, n2) {
      if (!n1Parent) {
        root = n2
      } else if (n1Parent.left == n1) {
        n1Parent.left = n2
      } else {
        n1Parent.right = n2
      }
    }

    function doGet() {
      clearStatus(root)
      const key = Number(document.getElementById("key").value)
      let node = root
      while (node != null) {
        if (key < node.txt) {
          node.status |= 2
          d.add({ cloned: clone(root) }, frame)
          node = node.left
        } else if (node.txt < key) {
          node.status |= 4
          d.add({ cloned: clone(root) }, frame)
          node = node.right
        } else {
          node.status |= 7
          d.add({ cloned: clone(root) }, frame)
          d.updateFrameButtons()
          return node
        }
      }
      d.updateFrameButtons()
      return null
    }

    function doPut() {
      clearStatus(root)
      const key = Number(document.getElementById("inserted").value)
      let node = root
      let parent = null
      while (node != null) {
        parent = node
        if (key < node.txt) {
          node.status |= 2
          d.add({ cloned: clone(root) }, frame)
          node = node.left
        } else if (node.txt < key) {
          node.status |= 4
          d.add({ cloned: clone(root) }, frame)
          node = node.right
        } else {
          node.status |= 7
          d.add({ cloned: clone(root) }, frame)
          d.updateFrameButtons()
          return
        }
      }
      if (parent == null) {
        root = { txt: key, status: 0 }
      } else if (parent.txt < key) {
        parent.right = { txt: key, status: 0 }
      } else {
        parent.left = { txt: key, status: 0 }
      }
      d.add({ cloned: clone(root) }, frame)
      d.updateFrameButtons()
      return null
    }

    function doPredecessor() {
      clearStatus(root)
      const key = Number(document.getElementById("key").value)
      let ancestorFromLeft = null
      let p = root
      while (p) {
        if (key < p.txt) {
          p.status |= 2
          p = p.left
          d.add({ cloned: clone(root), ancestorFromLeft: ancestorFromLeft ? ancestorFromLeft.txt : '' }, frame)
        } else if (p.txt < key) {
          ancestorFromLeft = p
          p.status |= 4
          p = p.right
          d.add({ cloned: clone(root), ancestorFromLeft: ancestorFromLeft ? ancestorFromLeft.txt : '' }, frame)
        } else {
          break
        }
      }
      if (!p) {
        return
      }
      p.status |= 7
      d.add({ cloned: clone(root), ancestorFromLeft: ancestorFromLeft ? ancestorFromLeft.txt : '' }, frame)
      if (p.left) {
        let successor = p.left
        while (successor.right != null) {
          successor = successor.right
        }
        successor.status |= 8
        d.add({ cloned: clone(root) }, frame)
        d.updateFrameButtons()
        return successor
      }
      if (ancestorFromLeft) {
        ancestorFromLeft.status |= 8
        d.add({ cloned: clone(root) }, frame)
        d.updateFrameButtons()
        return ancestorFromLeft
      }
      d.updateFrameButtons()
      return null
    }

    function doSuccessor() {
      clearStatus(root)
      const key = Number(document.getElementById("key").value)
      let ancestorFromRight = null
      let p = root
      while (p) {
        if (key < p.txt) {
          ancestorFromRight = p
          p.status |= 2
          p = p.left
          d.add({ cloned: clone(root), ancestorFromRight: ancestorFromRight ? ancestorFromRight.txt : '' }, frame)
        } else if (p.txt < key) {
          p.status |= 4
          p = p.right
          d.add({ cloned: clone(root), ancestorFromRight: ancestorFromRight ? ancestorFromRight.txt : '' }, frame)
        } else {
          break
        }
      }
      if (!p) {
        return
      }
      p.status |= 7
      d.add({ cloned: clone(root), ancestorFromRight: ancestorFromRight ? ancestorFromRight.txt : '' }, frame)
      if (p.right) {
        let successor = p.right
        while (successor.left != null) {
          successor = successor.left
        }
        successor.status |= 8
        d.add({ cloned: clone(root) }, frame)
        d.updateFrameButtons()
        return successor
      }
      if (ancestorFromRight) {
        ancestorFromRight.status |= 8
        d.add({ cloned: clone(root) }, frame)
        d.updateFrameButtons()
        return ancestorFromRight
      }
      d.updateFrameButtons()
      return null
    }

    function doMin() {
      clearStatus(root)
      let node = root
      while (node.left != null) {
        node.status |= 2
        d.add({ cloned: clone(root) }, frame)
        node = node.left
      }
      node.status |= 7
      d.add({ cloned: clone(root) }, frame)
      d.updateFrameButtons()
      return node.txt
    }

    function doMax() {
      clearStatus(root)
      let node = root
      while (node.right != null) {
        node.status |= 4
        d.add({ cloned: clone(root) }, frame)
        node = node.right
      }
      node.status |= 7
      d.add({ cloned: clone(root) }, frame)
      d.updateFrameButtons()
      return node.txt
    }

    function clearStatus(node) {
      if (!node) {
        return
      }
      node.status = 0
      clearStatus(node.left)
      clearStatus(node.right)
    }

    /*
      status
        0-都未处理
        1-节点自身处理完
        2-左孩子处理完
        4-右孩子处理完
    */
    // 根据 array 构造二叉树
    function binary_tree(array, n) {
      const newArray = array.map(e => e ? ({ txt: Number(e), status: 0 }) : null)
      const size = array.length
      for (let i = size - 1; i > 0; i--) {
        const pi = (i - 1) >> 1
        const parent = newArray[pi]
        if (parent != null) {
          const left = 2 * pi + 1
          const right = left + 1
          if (left === i) {
            parent.left = newArray[i]
          }
          if (right === i) {
            parent.right = newArray[i]
          }
        }
      }
      const root = newArray[0]
      d.add({ cloned: clone(root) }, frame)
      return root
    }

    function clone(tree) {
      return JSON.parse(JSON.stringify(tree))
    }

  </script>
</body>

</html>